package ext;

import util.TreeNode;
import java.util.*;

//打印 二叉树 中所有路径和为 sum的集合
public class AllSumPath {
    List<List<Integer>> res;
    int sum;
    public List<List<Integer>> allPath(TreeNode root, int sum) {
        res = new ArrayList<>();
        this.sum = sum;
        dfs(root, new ArrayList<>(), 0);
        return res;
    }

    private void dfs(TreeNode root, List<Integer> path, int cur) { 
        if (root == null) {
            if (sum == cur) {
                res.add(new ArrayList<>(path));
            }
            return;
        }
        cur += root.val;
        path.add(root.val);
        dfs(root.left, path, cur);
        dfs(root.right, path, cur);
        path.remove(path.size() - 1);
    }

    // class Info {
    //     List<Integer> path;
    //     int sum;

    //     public Info(List<Integer> path, int sum) {
    //         this.path = path;
    //         this.sum = sum;
    //     }
    // }

}
